Generic-case Complexity

Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs".

Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set of
unrepresentative inputs and considering worst-case complexity on the rest.
Small is defined in terms of asymptotic density.
The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy.

This approach to complexity originated in combinatorial group theory, which has a computational tradition going back to the beginning of the last century.
The notion of generic complexity was introduced in a 2003 paper,I. Kapovich, A. Myasnikov, P. Schupp and V. Shpilrain,
Generic case complexity, decision problems in group theory and random walks
', J. Algebra, vol 264 (2003), 665–694. where authors showed that for a large class of finitely generated groups the generic time complexity of some classical decision problems from combinatorial group theory, namely the word problem, conjugacy problem and membership problem, are linear.

A detailed introduction of generic case complexity can be found in the surveys.R. Gilman, A. G. Miasnikov, A. D. Myasnikov, and A. Ushakov, ''Generic Case Complexity'', unpublished first draft of a book, 143 pages.

Basic definitions

Asymptotic density

Let ''I'' be an infinite set of inputs for a computational problem.

Definition 1. A size function on ''I'' is a map $\sigma:I\to \mathbb$ with infinite range.
The ball of radius ''n'' is $B_n=\$.

If the inputs are coded as strings over a finite alphabet, size might be the string length.

Let $\$ be an ensemble of probability distributions where $\mu_n$ is a probability distribution on $B_n$.
If the balls $B_n$ are finite, then each $\mu_n$ can be taken to be the equiprobable distribution which is the most common case. Notice that only finitely many $B_n$'s can be empty or have $\mu_n(B_n) = 0$; we ignore them.

Definition 2. The asymptotic density of a subset $X \subset I$ is $\rho(X) = \lim_\mu_n(X \cap B_n)$ when this limit exists.

When the balls $B_n$ are finite and $\mu_n$ is the equiprobable measure,

: $\rho(X)=\lim \frac.$

In this case it is often convenient to use spheres $I_n=\$ instead of balls and define $\rho'(X)=\lim \frac$. An argument using Stolz theorem shows that $\rho(X)$ exists if $\rho'(X)$ does, and in that case they are equal.

Definition 3 $X\subseteq I$ is generic if $\rho(X)=1$ and negligible if $\rho(X)=0$.
''X'' is exponentially (superpolynomially) generic if the convergence to the limit in Definition 2 is exponentially (superpolynomially) fast, etc.

A generic subset ''X'' is asymptotically large. Whether ''X'' appears large in practice depends
on how fast $\mu_n(X\cap B_n)$ converges to 1. Superpolynomial convergence seems to be fast enough.

Generic complexity classes

Definition 4 An algorithm is in ''GenP'' (generically polynomial time) if it never gives incorrect answers and if it
gives correct answers in polynomial time on a generic set of inputs. A problem is in ''GenP'' if it
admits an algorithm in ''GenP''. Likewise for ''GenL'' (generically linear time), ''GenE'' (generically
exponential time with a linear exponent) ''GenExp'' (generically exponential time), etc.
''ExpGenP'' is the subclass of ''GenP'' for which the relevant generic set is exponentially generic.

More generally for any $f : \mathbb \to \mathbb$ we can define the class ''Gen(f)'' corresponding to
time complexity ''O''(''f'') on a generic set of input.

Definition 5. An algorithm solves a problem generically if it never gives incorrect answers and if it gives correct answers on a generic set of inputs. A problem is generically solvable if it is solved generically by some algorithm.

Theory and applications

Combinatorial group theory problems

* The famous undecidable problems: under suitable hypotheses, the word, conjugacy and membership decision problems are in generically polynomial.
* The word and conjugacy search problems are in ''GenP'' for all fixed finitely presented groups.

* The well known coset enumeration procedure admits a computable upper bound on a generic set of inputs.

* The Whitehead algorithm for testing whether or not one element of a free group is mapped to another by an automorphism has an exponential worst case upper bound but runs well in practice. The algorithm is shown to be in ''GenL''.

* The conjugacy problem in HNN extensions can be unsolvable even for free groups. However, it is generically cubic time.

The halting problem and the Post correspondence problem

* The halting problem for Turing machine with one-sided tape is easily decidable most of the time; it is in ''GenP''

The situation for two-sided tape is unknown. However, there is a kind of lower bound for machines of both types.
The halting problem is not in ''ExpGenP'' for any model of Turing machine,

* The Post correspondence problem is in ''ExpGenP''.

Presburger arithmetic

The decision problem for Presburger arithmetic admits a double exponential worst case lower bound and a triple exponential worst case upper bound. The generic complexity is not known, but it is known that the problem is not in ''ExpGenP''.

NP complete problems

As it is well known that NP-complete problems can be easy on average, it is not a surprise that several of them are generically easy too.

* The three satisfiability problem is in ''ExpGenP''.
* The subset sum problem is in ''GenP''.

One way functions

There is a generic complexity version of a one-way function which yields the same class of functions but allows one to consider different security assumptions than usual.

Public-key cryptography

A series of articles is devoted to cryptanalysis of the Anshel–Anshel–Goldfeld key exchange protocol, whose security is based on assumptions about the braid group. This series culminates in Miasnikov and Ushakov (2008) which applies techniques from generic case complexity to obtain a complete analysis of the length based attack and the conditions under which it works. The generic point of view also suggests a kind of new attack called the quotient attack, and a more secure version of the Anshel–Anshel–Goldfeld protocol.

List of general theoretical results

*A famous Rice's theorem states that if ''F'' is a subset of the set of partial computable functions from $\mathbb$ to $\$, then unless ''F'' or its complement is empty, the problem of deciding whether or not a particular Turing machine computes a function in ''F'' is undecidable. The following theorem gives a generic version.

Theorem 1 Let ''I'' be the set of all Turing machines. If ''F'' is a subset of the set of all
partial computable function from $\mathbb$ to itself such that ''F'' and its complement are both non-empty,
then the problem of deciding whether or not a given Turing machine computes a function from
''F'' is not decidable on any exponentially generic subset of ''I''.

* The following theorems are from:

Theorem 2 The set of formal languages which are generically computable has measure zero.

Theorem 3 There is an infinite hierarchy of generic complexity classes. More precisely for a proper complexity function ''f'', $Gen(f) \subsetneq Gen(f^3)$.

The next theorem shows that just as there are average case complete problems within distributional NP problems, there are also generic case complete problems. The arguments in the generic case are similar to those in the average case, and the generic case complete problem is also average case complete. It is the distributional bounded halting problem.

Theorem 4 There is a notion of generic-polynomial-time reduction with respect to which the distributional bounded halting problem is complete within class of distributional NP problems.

Comparisons with previous work

Almost polynomial time

Meyer and Paterson define an algorithm to be almost polynomial time, or APT, if it halts
within ''p(n)'' steps on all but ''p(n)'' inputs of size ''n''. Clearly, APT algorithms are included in our class ''GenP''. We have seen several NP complete problems in ''GenP'', but Meyer and Paterson show that this is not the case for APT. They prove that an NP complete problem is reducible to a problem in APT if and only if P = NP. Thus APT seems much more restrictive than ''GenP''.

Average-case complexity

Generic case complexity is similar to average-case complexity. However, there are some significant differences.
Generic case complexity is a direct measure of the performance of an algorithm on most inputs while average case complexity
gives a measure of the balance between easy and difficult instances. In addition Generic-case complexity naturally applies to undecidable problems.

Suppose $\mathcal$ is an algorithm whose time complexity, $T:I\to \mathbb$ is polynomial on $\mu$ average.
What can we infer about the behavior of $\mathcal$ on typical inputs?

Example 1 Let ''I'' be the set of all words over $\$ and define the size $\sigma(w)$ to be word length,
$, w,$. Define $I_n$ to be the set of words of length ''n'', and assume that each $\mu_n$ is the equiprobable measure.
Suppose that ''T(w)=n'' for all but one word in each $I_n$, and $T(w)=2^$ on the exceptional words.

In this example ''T'' is certainly polynomial on typical inputs, but ''T'' is not polynomial on average. ''T'' is in ''GenP''.

Example 2 Keep ''I'' and $\sigma(w) = , w,$ as before, but define $\mu(w)= 2^$ and
$T(w) = 2^$. ''T'' is polynomial on average even though it is exponential on typical inputs. ''T'' is not in ''GenP''.

In these two examples the generic complexity is more closely related to behavior
on typical inputs than average case complexity. Average case complexity measures something
else: the balance between the frequency of difficult instances and the degree of difficulty,.
Roughly speaking an algorithm which is polynomial time on average can have only a subpolynomial
fraction of inputs that require superpolynomial time to compute.

Nevertheless, in some cases generic and average case complexity are quite close to each other.
A function $f:I\rightarrow\mathbb^+$ is polynomial on $\mu$-average on spheres if there
exists $k \geq 1$ such that $\sum_ f^(w) \mu_n(w) = O(n)$ where $\$
is the ensemble induced by $\mu$. If ''f'' is polynomial on $\mu$-average on spheres, the ''f'' is
polynomial on $\mu$-average, and for many distributions the converse holds

Theorem 5 If a function $f:I\rightarrow \mathbb^+$ is polynomial on $\mu$-average on spheres then ''f''
is generically polynomial relative to the spherical asymptotic density $\rho'$.

Theorem 6 Suppose a complete algorithm $\mathcal$ has subexponential time bound ''T'' and a partial algorithm $\mathcal$
for the same problem is in ''ExpGenP'' with respect to the ensemble $\$ corresponding to a probability measure $\mu$
on the inputs ''I'' for $\mathcal$. Then there is a complete algorithm which is $\mu$-average time complexity.

Errorless heuristic algorithms

In a 2006 paper, Bogdanov and Trevisan came close to defining generic case complexity.A. Bogdanov, L. Trevisan, ''Average-case Complexity'', Found. Trends Theor. Comput. Sci. 2, No. 1, 111 p. (2006).. Instead of partial algorithms, they consider so-called errorless heuristic algorithms. These are
complete algorithms which may fail by halting with output "?". The class ''AvgnegP'' is defined
to consist of all errorless heuristic algorithms ''A'' which run in polynomial time and for which the
probability of failure on $I_n$ is negligible, i.e., converges superpolynomially fast to 0.
''AvgnegP'' is a subset of ''GenP''. Errorless heuristic algorithms are essentially the same as the algorithms with
benign faults defined by Impagliazzo where polynomial time on average algorithms are
characterized in terms of so-called benign algorithm schemes.

References

{{Reflist

Computational complexity theory